Graph splicing systems

In this paper, extended graph splicing systems are defined. It is shown that when strings are represented as linear graphs, any recursively enumerable set can be generated by an extended graph splicing system. It is also shown that the computational completeness of extended graph splicing systems can be proved under some constraints too.     

团复形是无圈的平面图是可伸缩图

许宝刚猜想:若图G的团复形是无圈的,则G为可伸缩图．本文证明了该猜想对平面图成立,即:若G是团复形为无圈的平面图,则G为可伸缩图．     

完备图分拆为带一条弦的(2k-1)-长圈

本文给出了构造G-设计的一个统一方法及当v≡1(mod 4k)时的C_(2k-1)~((r))-GD(v)的存在性,其中C_(10)~((r)),1≤r≤k-2表示带一条弦的2k-1长圈,r表示弦两个端点间的顶点个数。     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

关于二部图Km1m2-Hm2的升分解

在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD)，并提出了一个猜想：任意有正数条边的图都可以升分解．本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解，其中Hm2是至多含m2条边的Km1m2的子图．     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。     

On the Hamilton-Jacobi Treatment of Constrained Systems

Systems with singular-higher order Lagrangians are investigated by two methods: Dirac method and Hamilton-Jacobi method. An example is studied and it is shown that the Hamilton-Jacobi method gives the correct canonical generalized equations of motion, contrary to Dirac method, where Dirac conjecture is invalid.     

有向图上的随机游动

设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.     

子图识别的层分解方法

子图识别问题(SRP)就是在一个图G中确定并寻找是否存在和另一个图H相同构的子图．本文将引入图的层分解概念，并以此为基础建立识别图的同构子图的算法．该算法的复杂性为O(n(△-1)^k-1)，其中△是图G的度，即G中点的最大度，n，k分别是图G，H的阶．